/// 链表元素比较函数类型
///
/// # 参数
/// - `value1`: 第一个待比较元素的不可变引用
/// - `value2`: 第二个待比较元素的不可变引用
///
/// # 返回值
/// 返回排序顺序标识：
/// - 负数表示 value1 应排在 value2 之前
/// - 零表示两者相等
/// - 正数表示 value1 应排在 value2 之后
pub type SListCompareFunc<T> = fn(value1: &T, value2: &T) -> std::cmp::Ordering;

/// 链表元素相等判断函数类型
///
/// # 参数
/// - `value1`: 第一个待比较元素的不可变引用
/// - `value2`: 第二个待比较元素的不可变引用
///
/// # 返回值
/// 返回相等性判断结果：
/// - 非零值表示相等
/// - 零值表示不等
pub type SListEqualFunc<T> = fn(value1: &T, value2: &T) -> i32;

/// 单向链表节点结构体
///
/// # 泛型参数
/// - `T`: 链表节点存储的数据类型
#[derive(Debug, Clone)]
pub struct SListEntry<T> {
    /// 节点存储的数据
    pub data: T,
    /// 指向下一个节点的可选智能指针
    pub next: Option<Box<SListEntry<T>>>,
}

/// 从链表中移除所有匹配给定数据的节点
///
/// # 参数
/// - `head`: 链表头节点的可变引用
/// - `eq_func`: 相等性判断函数
/// - `target`: 要匹配的目标数据引用
///
/// # 返回值
/// 返回被移除的节点数量
pub fn slist_remove_data<T>(
    head: &mut Option<Box<SListEntry<T>>>,
    eq_func: SListEqualFunc<T>,
    target: &T
) -> usize {
    let mut removed = 0;
    let mut curr = head;

    loop {
        let should_remove = match curr.as_ref() {
            Some(node) => eq_func(&node.data, target) != 0,
            None => break,
        };

        if should_remove {
            // 取出当前节点并替换为下一个节点
            let mut node = curr.take().unwrap();
            let next = node.next.take();
            *curr = next;
            removed += 1;
        } else {
            // 移动到下一个节点
            curr = &mut curr.as_mut().unwrap().next;
        }
    }

    removed
}


/// 获取链表中第n个节点的不可变引用
///
/// # 参数
/// - `list`: 链表头节点的可选智能指针引用
/// - `n`: 要获取的节点索引（从0开始计数）
///
/// # 返回值
/// 返回`Option<&SListEntry<T>>`：
/// - Some(节点引用) 当索引有效时
/// - None 当索引越界或链表为空时
pub fn slist_nth_entry<T>(list: &Option<Box<SListEntry<T>>>, n: usize) -> Option<&SListEntry<T>> {
    let mut current = list.as_deref();
    
    for _ in 0..n {
        current = current.and_then(|entry| entry.next.as_deref());
    }
    current
}

/// 获取链表中第n个节点存储的数据
///
/// # 参数
/// - `list`: 链表头节点的可选智能指针引用
/// - `n`: 要获取的数据索引（从0开始计数）
///
/// # 返回值
/// 返回`Option<&T>`：
/// - Some(数据引用) 当索引有效时
/// - None 当索引越界或链表为空时
pub fn slist_nth_data<T>(list: &Option<Box<SListEntry<T>>>, n: usize) -> Option<&T> {
    slist_nth_entry(list, n).map(|entry| &entry.data)
}


/// Prepends an element to the beginning of the singly linked list
///
/// # Parameters
/// - `list`: Mutable reference to the head pointer of the linked list
/// - `data`: Data to store in the new element
///
/// # Returns
/// Mutable reference to the newly created list entry
pub fn slist_prepend<T>(list: &mut Option<Box<SListEntry<T>>>, data: T) -> Option<&mut SListEntry<T>> {
    let next = list.take();
    *list = Some(Box::new(SListEntry { data, next }));
    Some(list.as_mut().unwrap())
}

/// 使用快速排序算法对链表进行内部排序
///
/// # 参数
/// - `list`: 链表头节点的可变引用
/// - `compare_func`: 元素比较函数
///
/// # 返回值
/// 返回排序后链表的最后一个节点引用
fn slist_sort_internal<T>(
    head: Option<Box<SListEntry<T>>>,
    compare_func: SListCompareFunc<T>,
) -> Option<Box<SListEntry<T>>> {
    let mut head = match head {
        Some(mut pivot) => {
            // 基本情况处理：单节点链表直接返回
            if pivot.next.is_none() {
                return Some(pivot);
            }

            let pivot_data = &pivot.data;
            let mut less = None;
            let mut more = None;

            // 分割剩余节点到less和more链表
            let mut current = pivot.next.take();
            while let Some(mut node) = current {
                let next = node.next.take();
                if compare_func(&node.data, pivot_data).is_le() {
                    node.next = less.take();
                    less = Some(node);
                } else {
                    node.next = more.take();
                    more = Some(node);
                }
                current = next;
            }

            // 递归排序子链表
            let less = slist_sort_internal(less, compare_func);
            let more = slist_sort_internal(more, compare_func);

            // 构建排序后的链表
            let mut new_head = less;
            if let Some(mut less_tail) = new_head.as_mut() {
                // 找到less链表的最后一个节点
                while let Some(ref mut next) = less_tail.next {
                    less_tail = next;
                }
                // 将pivot连接到less链表末尾
                less_tail.next = Some(pivot);
            } else {
                new_head = Some(pivot);
            }

            // 将more链表连接到pivot后面
            if let Some(mut new_head_node) = new_head.as_mut() {
                // 找到当前链表的最后一个节点（pivot节点）
                let mut current = new_head_node;
                while let Some(ref mut next) = current.next {
                    current = next;
                }
                current.next = more;
            }

            new_head
        }
        None => None,
    };

    head
}

/// 对链表进行排序的入口函数
///
/// # 参数
/// - `list`: 链表头节点的可变引用
/// - `compare_func`: 元素比较函数
pub fn slist_sort<T>(
    list: &mut Option<Box<SListEntry<T>>>,
    compare_func: SListCompareFunc<T>,
) {
    *list = slist_sort_internal(list.take(), compare_func);
}

/// 对链表进行排序的入口函数
///
/// # 参数
/// - `list`: 链表头节点的可变引用
/// - `compare_func`: 元素比较函数
/// 从链表中移除指定的节点
///
/// # 参数
/// - `list`: 链表头节点的可变引用
/// - `entry`: 要移除的节点裸指针（需确保属于该链表）
///
/// # 返回值
/// 返回操作是否成功：
/// - true 表示节点找到并成功移除
/// - false 表示链表为空或节点未找到
pub fn slist_remove_entry<T>(
    list: &mut Option<Box<SListEntry<T>>>,
    entry: *const SListEntry<T>,
) -> bool {
    // 处理空链表或无效指针输入
    if list.is_none() || entry.is_null() {
        return false;
    }

    // 检查头节点是否为目标节点
    if let Some(head) = list.as_ref() {
        if std::ptr::eq(head.as_ref(), entry) {
            *list = list.take().unwrap().next;
            return true;
        }
    }

    // 遍历链表寻找前驱节点
    let mut curr = list.as_mut().unwrap();
    while let Some(next_node) = curr.next.as_mut() {
        if std::ptr::eq(next_node.as_ref(), entry) {
            // 找到目标节点并重新链接链表
            let target = curr.next.take().unwrap();
            curr.next = target.next;
            return true;
        }
        curr = curr.next.as_mut().unwrap();
    }

    false
}

/// 在链表中查找包含指定数据的节点
///
/// # 参数
/// - `list`: 链表头节点的可选智能指针引用
/// - `eq_func`: 相等性判断函数
/// - `target`: 要匹配的目标数据引用
///
/// # 返回值
/// 返回`Option<&SListEntry<T>>`：
/// - Some(节点引用) 当找到匹配数据时
/// - None 当未找到匹配数据或链表为空时
pub fn slist_find_data<'a, T>(
    list: &'a Option<Box<SListEntry<T>>>,
    eq_func: SListEqualFunc<T>,
    target: &'a T
) -> Option<&'a SListEntry<T>> {
    let mut current = list.as_deref();

    while let Some(entry) = current {
        if eq_func(&entry.data, target) != 0 {
            return Some(entry);
        }
        current = entry.next.as_deref();
    }

    None
}

/// 释放整个链表及其所有节点
///
/// # 参数
/// - `list`: 链表头节点的可变引用，函数执行后链表指针将被设置为 None
pub fn slist_free<T>(list: &mut Option<Box<SListEntry<T>>>) {
    *list = None;
}

/// 单向链表迭代器结构体
///
/// # 泛型参数
/// - `T`: 链表节点存储的数据类型
///
/// # 安全说明
/// 使用裸指针实现链表遍历和修改操作，调用者需保证指针有效性
/// 单向链表迭代器结构体
///
/// # 泛型参数
/// - `T`: 链表节点存储的数据类型
///
/// # 安全说明
/// 使用裸指针实现链表遍历和修改操作，调用者需保证指针有效性
#[derive(Debug)]
pub struct SListIterator<T> {
    /// 前驱节点的next字段指针
    prev_next: *mut Option<Box<SListEntry<T>>>,
    /// 当前节点的可变指针
    current: *mut SListEntry<T>,
}

impl<T> SListIterator<T> {
    /// 创建新的链表迭代器
    ///
    /// # 参数
    /// - `head`: 链表头节点的可变引用
    pub fn new(head: &mut Option<Box<SListEntry<T>>>) -> Self {
        let prev_next = head as *mut _;
        let current = std::ptr::null_mut();
        Self { prev_next, current }
    }

    /// 获取当前节点数据引用
    pub fn current(&self) -> Option<&T> {
        if self.current.is_null() {
            None
        } else {
            // 安全：指针有效性由迭代器使用保证
            Some(unsafe { &(*self.current).data })
        }
    }

    /// 移动到下一个节点
    pub fn move_next(&mut self) {
        if self.current.is_null() {
            return;
        }

        // 安全：指针有效性由迭代器使用保证
        let current = unsafe { &mut *self.current };
        self.prev_next = &mut current.next as *mut _;
        self.current = current.next
            .as_deref_mut()
            .map(|n| n as *mut _)
            .unwrap_or(std::ptr::null_mut());
    }

    /// 移除当前节点并返回数据
    ///
    /// # 安全
    /// 调用者必须确保迭代器当前指向有效节点
    pub unsafe fn remove_current(&mut self) -> Option<T> {
        if self.current.is_null() {
            return None;
        }

        let prev_next = &mut *self.prev_next;
        prev_next.take().map(|mut node| {
            let next = node.next.take();
            *prev_next = next;
            self.current = prev_next.as_deref_mut().map(|n| n as *mut _).unwrap_or(std::ptr::null_mut());
            node.data
        })
    }

    /// 判断迭代器是否还有更多可遍历元素
    ///
    /// # 安全
    /// 调用者必须保证迭代器处于有效状态
    ///
    /// # 返回值
    /// 返回布尔值：
    /// - true 表示存在后续可访问元素
    /// - false 表示已到达链表末尾
    pub unsafe fn has_more(&self) -> bool {
        !(*self.prev_next).is_none()
    }

    /// 获取迭代器的下一个元素
    ///
    /// # 安全
    /// 调用者必须保证迭代器处于有效状态
    ///
    /// # 返回值
    /// 返回`Option<&T>`：
    /// - Some(数据引用) 当存在后续元素时
    /// - None 当到达链表末尾时
    pub fn next(&mut self) -> Option<&T> {
        unsafe {
            // 从prev_next获取当前节点
            let current_entry = (*self.prev_next).as_deref_mut()?;
            self.current = current_entry as *mut _;
            // 将prev_next更新为当前节点的next字段的指针
            let current = &mut *self.current;
            self.prev_next = &mut current.next as *mut _;
            Some(&current.data)
        }
    }

    /// 移除迭代器当前指向的链表节点
    ///
    /// # 安全
    /// 调用者必须确保迭代器处于有效状态且当前节点属于链表
    pub unsafe fn remove(&mut self) {
        if self.current.is_null() {
            return;
        }

        // 取出当前节点的next
        let current = &mut *self.current;
        let next = current.next.take();
        // 将前驱节点的next指向next
        *self.prev_next = next;
        // 当前节点被删除，current置为null
        self.current = std::ptr::null_mut();
    }
}
impl<T> SListEntry<T> {
    /// 获取当前节点的下一个节点引用
    ///
    /// # 参数
    /// - `&self`: 当前节点的不可变引用
    ///
    /// # 返回值
    /// 返回`Option<&SListEntry<T>>`：
    /// - Some(下一个节点引用) 当存在后续节点时
    /// - None 当到达链表末尾时
    pub fn next(&self) -> Option<&SListEntry<T>> {
        self.next.as_deref()
    }

    /// 获取当前节点存储的数据引用
    ///
    /// # 参数
    /// - `&self`: 当前节点的不可变引用
    ///
    /// # 返回值
    /// 返回`&T`类型的数据引用
    pub fn data(&self) -> &T {
        &self.data
    }

    /// 设置当前节点存储的数据
    ///
    /// # 参数
    /// - `&mut self`: 当前节点的可变引用
    /// - `data`: 要存储的新数据
    pub fn set_data(&mut self, data: T) {
        self.data = data;
    }
}
pub fn slist_next<T>(entry: &SListEntry<T>) -> Option<&SListEntry<T>> {
    entry.next.as_deref()
}
///
/// # 参数
/// - `list`: 链表头节点的可变引用
/// - `data`: 要存储到新元素的数据
///
/// # 返回值
/// 返回新创建节点的可变引用
pub fn slist_append<T>(
    list: &mut Option<Box<SListEntry<T>>>,
    data: T
) -> Option<&mut SListEntry<T>> {
    let new_entry = Box::new(SListEntry {
        data,
        next: None,
    });

    if list.is_none() {
        *list = Some(new_entry);
        return Some(list.as_mut().unwrap());
    }

    let mut curr = list.as_mut().unwrap();
    while curr.next.is_some() {
        curr = curr.next.as_mut().unwrap();
    }

    curr.next = Some(new_entry);
    Some(curr.next.as_mut().unwrap())
}

/// 获取链表的节点数量
///
/// # 参数
/// - `list`: 链表头节点的可选智能指针引用
///
/// # 返回值
/// 返回链表中包含的节点总数
pub fn slist_length<T>(list: &Option<Box<SListEntry<T>>>) -> usize {
    let mut count = 0;
    let mut current = list.as_deref();

    while let Some(entry) = current {
        count += 1;
        current = entry.next.as_deref();
    }

    count
}

/// 将链表转换为包含所有数据的动态数组
///
/// # 参数
/// - `list`: 链表头节点的可选智能指针引用
///
/// # 返回值
/// 返回包含链表所有数据的 `Vec<T>`，元素顺序与链表节点顺序一致
pub fn slist_to_array<T: Clone>(list: &Option<Box<SListEntry<T>>>) -> Vec<T> {
    let length = slist_length(list);
    let mut array = Vec::with_capacity(length);
    
    let mut current = list.as_deref();
    while let Some(entry) = current {
        array.push(entry.data.clone());
        current = entry.next.as_deref();
    }

    array
}